#include <iostream>
#include "RedBlackTree.h"
#include "BTree.h"
#include "BPlusTree.h"

void testRedBlackTree() {
    std::cout << "=== 红黑树测试 ===" << std::endl;
    RedBlackTree<int> rbt;
    
    // 插入测试
    std::cout << "插入元素: 7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13" << std::endl;
    int values[] = {7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13};
    for (int val : values) {
        rbt.insert(val);
    }
    
    std::cout << "红黑树中序遍历: ";
    rbt.print();
    
    // 查找测试
    std::cout << "查找 10: " << (rbt.search(10) ? "找到" : "未找到") << std::endl;
    std::cout << "查找 15: " << (rbt.search(15) ? "找到" : "未找到") << std::endl;
    
    // 删除测试
    std::cout << "删除元素 18" << std::endl;
    rbt.remove(18);
    std::cout << "删除后的红黑树: ";
    rbt.print();
    
    std::cout << std::endl;
}

void testBTree() {
    std::cout << "=== B树测试 ===" << std::endl;
    BTree<int> bt(3);
    
    // 插入测试
    std::cout << "插入元素: 1, 3, 7, 10, 11, 13, 14, 15, 18, 16, 19, 24, 25, 26, 21, 4, 5, 20, 22, 2, 17, 12, 6" << std::endl;
    int values[] = {1, 3, 7, 10, 11, 13, 14, 15, 18, 16, 19, 24, 25, 26, 21, 4, 5, 20, 22, 2, 17, 12, 6};
    for (int val : values) {
        bt.insert(val);
    }
    
    std::cout << "B树结构:" << std::endl;
    bt.print();
    
    // 查找测试
    std::cout << "查找 10: " << (bt.search(10) ? "找到" : "未找到") << std::endl;
    std::cout << "查找 15: " << (bt.search(15) ? "找到" : "未找到") << std::endl;
    std::cout << "查找 30: " << (bt.search(30) ? "找到" : "未找到") << std::endl;
    
    // 删除测试
    std::cout << "删除元素 6" << std::endl;
    bt.remove(6);
    std::cout << "删除后的B树:" << std::endl;
    bt.print();
    
    std::cout << std::endl;
}

void testBPlusTree() {
    std::cout << "=== B+树测试 ===" << std::endl;
    BPlusTree<int> bpt(3);
    
    // 插入测试
    std::cout << "插入元素: 5, 9, 3, 7, 1, 2, 8, 6, 4" << std::endl;
    int values[] = {5, 9, 3, 7, 1, 2, 8, 6, 4};
    for (int val : values) {
        bpt.insert(val);
    }
    
    std::cout << "B+树结构:" << std::endl;
    bpt.print();
    
    std::cout << "叶子节点链表: ";
    bpt.printLeafList();
    
    // 查找测试
    std::cout << "查找 5: " << (bpt.search(5) ? "找到" : "未找到") << std::endl;
    std::cout << "查找 10: " << (bpt.search(10) ? "找到" : "未找到") << std::endl;
    
    // 删除测试
    std::cout << "删除元素 3" << std::endl;
    bpt.remove(3);
    std::cout << "删除后的B+树:" << std::endl;
    bpt.print();
    std::cout << "删除后的叶子节点链表: ";
    bpt.printLeafList();
    
    std::cout << std::endl;
}

int main() {
    std::cout << "树结构实现测试程序" << std::endl;
    std::cout << "==================" << std::endl << std::endl;
    
    testRedBlackTree();
    testBTree();
    testBPlusTree();
    
    std::cout << "所有测试完成！" << std::endl;
    return 0;
} 